#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <algorithm>

class Solution1
{
public:
    std::vector<int> twoSum(std::vector<int>& nums, int target)
    {
        // 思路：对数组进行升序排序，然后采用双指针
        // i,j分别从左右边界开始寻找
        // 如果和小于target，则i++
        // 如果和大于target，则j--
        // 如果和等于target，则break,并返回结果
        // 注意：需要在排序过程中，记录原始下标位置

        std::vector<std::pair<int, int>> tmp;
        for (int i = 0; i < nums.size(); i++)
        {
            tmp.emplace_back(nums[i], i);
        }
        sort(tmp.begin(), tmp.end(), [](const std::pair<int, int>& p1, const std::pair<int, int>& p2) {
            return p1.first < p2.first;
            });

        for (auto& [a, b] : tmp) {
            std::cout << a << " " << b << std::endl;
        }

        int i = 0, j = tmp.size() - 1;
        while (i < j) {
            if (tmp[i].first + tmp[j].first < target) i++;
            else if (tmp[i].first + tmp[j].first > target) j--;
            else break;
        }

        return { tmp[i].second, tmp[j].second };
    }
};

class Solution2
{
public:
    std::vector<int> twoSum(std::vector<int>& nums, int target)
    {
        // 借助哈希表，寻找两数之和为target，其实就是在寻找一个数y，等于 target - x     
        // 所以，我们可以通过哈希表，快速查找target - x这个数
        std::unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); i++) {
            auto iter = hash.find(target - nums[i]);
            if (iter != hash.end()) {
                return { i, iter->second };
            }
            hash[nums[i]] = i;
        }
        return {};
    }
};

class Solution3
{
public:
    std::vector<std::vector<std::string>> groupAnagrams(std::vector<std::string>& strs)
    {
        // 1.遍历原字符串数组，对字符串进行排序，如果排序后的字符串相等，则插入同一个字符串数组中
        std::unordered_map<std::string, std::vector<std::string>> hash;
        for (auto& s : strs) {
            std::string tmp = s;
            sort(tmp.begin(), tmp.end());
            hash[tmp].emplace_back(s);
        }

        // 2.统计结果
        std::vector<std::vector<std::string>> ret;
        for (auto& [a, b] : hash) {
            ret.emplace_back(b);
        }

        return ret;
    }
};


class Solution3
{
public:
    int longestConsecutive(std::vector<int>& nums)
    {
        // 思路：
        // 1.数组中有重复元素，首先通过set天然去重
        // 2.遍历哈希表，首先判断该数有没有可能是一个序列的开头
        //     如果不是开头，则直接跳过该元素
        //     如果是开头，则循环找它的下一个数，并记录个数

        std::unordered_set<int> st;
        for (const int e : nums) st.insert(e);

        int ret = 0;
        for (const int num : st) {
            // 如果这个数是一个序列的开头，则继续在哈希表中搜索是否还有连续序列
            if (!st.count(num - 1)) {
                int currentNum = num;
                int currentCount = 1;
                while (st.count(currentNum + 1)) {
                    currentCount++;
                    currentNum += 1;
                }

                ret = std::max(ret, currentCount);
            }
        }
        return ret;
    }
};

class Solution4
{
public:
    void moveZeroes(std::vector<int>& nums)
    {
        // 数组分块，利用j将已经遍历过的元素分为非0和0
        // 遍历到0元素，i++
        // 遍历到非0元素，与++j位置进行交换（j是最后一个非0元素，++j即第一个0）

        int i = 0, j = -1; // 用i来遍历元素，j用来区分非0元素与0元素边界
        while (i < nums.size()) {
            if (nums[i] != 0) {
                std::swap(nums[++j], nums[i]);
            }
            i++;
        }
    }
};

class Solution5
{
public:
    int maxArea(std::vector<int>& height)
    {
        // 简而言之，刚开始每个元素都可以作为边界
        // 但是在过程中，如果短的板不移动，则新计算出来的结果只能比上一次的小（距离变小，高度最大就是上一次的高度，所以结果永远都小于上一次）
        // 所以，在遍历过程中，计算一次之后，让短的板向另一个指针方向移动

        int maxSize = 0;
        int i = 0, j = height.size() - 1;
        while (i < j) {
            int area = (j - i) * (std::min(height[i], height[j]));
            maxSize = std::max(area, maxSize);

            if (height[i] <= height[j]) {
                i++;
            }
            else {
                j--;
            }
        }
        return maxSize;
    }
};


class Solution6
{
public:
    std::vector<std::vector<int>> threeSum(std::vector<int>& nums)
    {
        // 对数组进行排序，然后固定一个数，再剩余区间使用双指针，找两数之和为-x
        sort(nums.begin(), nums.end());
        std::vector<std::vector<int>> ret;
        int n = nums.size(), i = 0;

        while (i < n) {// 枚举第一个数
            if (nums[i] > 0) break; // 如果nums[i]大于0，则后面的数都大于0，不可能出现和为0的情况

            // 使用双指针，找剩余区间的两数之和
            int target = nums[i] * -1;

            int j = i + 1, k = n - 1;
            while (j < k) {
                if (nums[j] + nums[k] > target) k--;
                else if (nums[j] + nums[k] < target) j++;
                else {
                    ret.push_back({ nums[i], nums[j], nums[k] });

                    // 跳过j、k，继续查找是否还存在和为target的值
                    // 跳过相等的值
                    int old_j = j++;
                    int old_k = k--;
                    while (j < k && nums[j] == nums[old_j]) j++;
                    while (j < k && nums[k] == nums[old_k]) k--;
                }
            }

            // 找到下一个target，注意跳过重复元素
            i++;
            while (i < n && nums[i] == target * -1) i++;
        }
        return ret;
    }
};


int main()
{
	return 0;
}